// https://leetcode.cn/problems/guess-number-higher-or-lower-ii/submissions/
// Created by ade on 2022/11/22.
//
#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    int getMoneyAmount(int n) {
        //f[i][n] = min(j+max(f[i][j-1], f[j+1][n]),f[i][n]);
        //f[i][j] = min(k+max(f[i][k-1], f[k+1][j]),f[i][j]);
        if (n <= 3) return n - 1;
        vector <vector<int>> dp(n + 1, vector<int>(n + 1));
        for (int right = 2; right <= n; right++) {
            for (int left = right - 1; left >= 1; left--) {
                int ans = INT_MAX;
                for (int i = left + 1; i < right; i++) {
                    ans = min(ans, i + max(dp[left][i - 1], dp[i + 1][right]));
                }
                // 处理边界
                ans = min(ans, left + dp[left + 1][right]);
                ans = min(ans, right + dp[left][right - 1]);
                dp[left][right] = ans;
            }
        }

        return dp[1][n];
    }
};

int main() {
    Solution so;
    cout << so.getMoneyAmount(10) << endl;
    return 0;
}